package com.li.suanfa;

import java.util.Arrays;
import java.util.Random;

/**  
 * 类说明   
 *  
 * @author ****  
 * @date 2018年4月1日  新建  
 */
public class QuickSort {
	public static final int SIZE = 10;
	public static void main(String[] args) {
		int[] array = new int[SIZE];
		Random random = new Random();
		for(int i = 0;i < SIZE ;i++){
			array[i] = random.nextInt(100);
		}
		
		System.out.println(Arrays.toString(array));
		
		long time1= System.currentTimeMillis();
		System.out.println("##############################################");
		quickSort(array,0,array.length-1);
		System.out.println(Arrays.toString(array));
		System.out.println(System.currentTimeMillis()-time1);
	}

	public static void quickSort(int[] a,int low, int high){
		if(low>=high){
			return;
		}
		int mid = partion(a, low, high);
		quickSort(a, low, mid-1);
		quickSort(a, mid+1, high);
	}

	public static int partion(int[] a,int low,int high){
		int mid = a[low];
		while(high>low){
			while(a[high]>=mid && high>low){
				high--;
			}
			a[low] = a[high];
			while(a[low]<=mid && high>low){
				low++;
			}
			a[high] = a[low];
		}
		a[low] = mid;
		return low;
	}
}
